Test 0120 summary

T1 分段 DP

Description

给定长度为 nn 的单调不减序列 {a}\{a\} 。定义一个区间的权值为区间长度与区间最小值的乘积。求将该序列分成 k[1,n]k\in [1,n] 段的权值和的最大值。
1n2×105,1ai8×1031\leq n\leq 2\times 10^5,1\leq a_i\leq 8\times 10^3

阅读全文 »

CF379F New Year Tree 解题报告

Description

有一棵树,初始时只有 44 个节点, 2 3 42\ 3\ 4 的父节点都是 11qq 次操作,每次给定一个点 uu 。设操作前点数为 nn ,那么本次操作就是将 n+1n+1n+2n+2 连在 uu 上。操作后输出目前树的直径大小。

q5×105q\leq 5\times 10^5

Solution

阅读全文 »

dijkstra 算法求费用流

众所周知,在求解费用流的时由于要建反边,必然会有负权边的存在。所以费用流的通常写法是 EK+SPFA。
事实上我们是可以通过一些技巧,使得 dijkstra 也可以跑费用流。这样的好处是保证了复杂度的下限。
本文将探讨如何使得 dijkstra 可以跑费用流。


阅读全文 »

拟阵及拟阵交

定义

定义 EE 为基础集,I\mathcal{I} 是由 EE 的子集构成的集族(子集的集合)。
元组 (E,I)(E,\mathcal{I}) 构成了一个子集系统,当且仅当

DP 杂题泛做

T1

Description

给一个数列,长度为 10510^5 。划成 2020 段,每段权值为 #{i,jai=aj}\{i,j|a_i=a_j\}。要求最小化权值和。

Solution

阅读全文 »

HNOI2016 解题报告

T1 大数

Description

给定一个长度为 nn 的十进制数 s 和一个质数 ppqq 次询问,每次给定 l rl\ r ,询问有多少十进制数 s[x:y] (lxyr)(l\leq x\leq y\leq r) 能被 pp 整除。
1n,q2×105,p2×1091\leq n,q\leq 2\times 10^5,p\leq 2\times 10^9

阅读全文 »

SPOJ3734 Periodni 解题报告

Description

给定一个 nn 列的表格,每列的高度 hih_i 各不相同,但底部对齐,然后向表格中填入 kk 个相同的数,填写时要求不能有两个数在同一列。若两个数在同一行,但是中间某一列断开是被允许的,否则也不允许。求填数的方案数对 109+710^9+7 取模的值。
n500,hi106n\leq 500,h_i\leq 10^6

Solution

阅读全文 »

HNOI2015 解题报告

T1 菜肴制作

Description

nn 道菜和有 mm 条要求,每条要求形如“A 号菜需要在 B 号菜的前面”。现在要求给出一个上菜序列,在满足所有要求的前提下,满足:

CF932G Palindrome Partition 解题报告

Description

给定一个串,把串分成偶数段,假设为 s1,s2,,sks_1,s_2,\cdots,s_k ,要求满足 s1=sk,s2=sk1,s_1=s_k,s_2=s_{k-1},\cdots ,求方案数。
n105n\leq 10^5

Solution

阅读全文 »